import java.util.*;

/**
 * 使用邻接矩阵来存储图
 */
public class GraphByMatrix {
    private char[] arrayV; // 顶点数组
    private int[][] matrix; // 邻接矩阵
    private boolean isDirect; // 表示是有向图/无向图

    public GraphByMatrix(int size, boolean isDirect){
        this.arrayV = new char[size];
        this.matrix = new int[size][size];
        for(int i = 0; i < size; i++){
            Arrays.fill(matrix[i], Integer.MAX_VALUE);
        }
        this.isDirect = isDirect;
    }

    // 初始化顶点数组
    public void initArrayV(char[] array){
        int n = this.arrayV.length;
        for(int i = 0; i < n; i++){
            this.arrayV[i] = array[i];
        }
    }

    public void addEdge(char srcV, char destV, int weight){
        int src = getIndexOfV(srcV);
        int dest = getIndexOfV(destV);

        if(src == -1 || dest == -1){
            return;
        }

        matrix[src][dest] = weight;

        if(!isDirect){
            matrix[dest][src] = weight;
        }
    }

    private int getIndexOfV(int v){
        int n = this.arrayV.length;
        for(int i = 0; i < n; i++){
            if(this.arrayV[i] == v){
                return i;
            }
        }
        return -1;
    }

    public int getDevOfV(char v){
        int n = this.arrayV.length;
        int count = 0;

        int index = getIndexOfV(v);

        for(int i = 0; i < n; i++){
            if(matrix[index][i] != Integer.MAX_VALUE){
                count++;
            }
        }

        // 如果是有向图，需要计算入度
        if(isDirect){
            for(int i = 0; i < n; i++){
                if(i == index){
                    continue;
                }else{
                    if(matrix[i][index] != Integer.MAX_VALUE){
                        count++;
                    }
                }
            }
        }

        return count;
    }

    public void printGraph(){
        int n = this.arrayV.length;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(matrix[i][j] == Integer.MAX_VALUE){
                    System.out.print("∞" + " ");
                }else{
                    System.out.print(matrix[i][j] + " ");
                }
            }
            System.out.println();
        }
    }

    // 图的遍历
    public void bfs(char v){
        int n = this.arrayV.length;
        Queue<Character> queue = new LinkedList<>();
        boolean[] check = new boolean[n];

        queue.offer(v);
        int indexV = getIndexOfV(v);
        check[indexV] = true;
        while(!queue.isEmpty()){
            char ch = queue.poll();
            System.out.print(ch + " ");
            int index = getIndexOfV(ch);
            for(int i = 0; i < n; i++){
                if(!check[i] && matrix[index][i] != Integer.MAX_VALUE){
                    queue.offer(this.arrayV[i]);
                    check[i] = true;
                }
            }
        }
        System.out.println();
    }

    public void dfs(char v){
        boolean[] check = new boolean[this.arrayV.length];
        int index = getIndexOfV(v);

        dfsChild(index, check);
    }

    public void dfsChild(int index, boolean[] check){
        System.out.print(this.arrayV[index] + " ");
        check[index] = true;
        for(int i = 0; i < this.arrayV.length; i++){
            if(!check[i] && matrix[index][i] != Integer.MAX_VALUE){
                dfsChild(i, check);
            }
        }
    }

    // 求最小生成树
    static class Edge{
        public int srcIndex;
        public int destIndex;
        public int weight;

        public Edge(int srcIndex, int destIndex, int weight){
            this.srcIndex = srcIndex;
            this.destIndex = destIndex;
            this.weight = weight;
        }
    }

    public int kruskal(GraphByMatrix minTree){
        int n = this.arrayV.length;
        // 1. 建小根堆 - 每次找到最小的边
        PriorityQueue<Edge> minQ = new PriorityQueue<>((a, b) -> a.weight - b.weight);
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                if(matrix[i][j] != Integer.MAX_VALUE){
                    Edge edge = new Edge(i, j, matrix[i][j]);
                    minQ.offer(edge);
                }
            }
        }
        // 2. 每次拿到最小的边，判断是否在一个集合中
        int count = 0;
        UnionFindSet ufs = new UnionFindSet(n);
        int totalWeight = 0;

        while(count < n - 1 && !minQ.isEmpty()){
            Edge edge = minQ.poll();

            if(!ufs.isSameUnionFindSet(edge.srcIndex, edge.destIndex)){
                minTree.addEdgeByIndex(edge.srcIndex, edge.destIndex, edge.weight);

                ufs.union(edge.srcIndex, edge.destIndex);
                totalWeight += edge.weight;
                count++;

                if(count == n - 1){
                    return totalWeight;
                }
            }
        }

        return -1;
    }

    private void addEdgeByIndex(int srcIndex, int destIndex, int weight){
        matrix[srcIndex][destIndex] = weight;

        if(!isDirect){
            matrix[destIndex][srcIndex] = weight;
        }
    }

    public int prime(GraphByMatrix minTree, char chV){
        int n = this.arrayV.length;
        // 1. 存放开始顶点
        int index = getIndexOfV(chV);
        Set<Integer> setX = new HashSet<>();
        setX.add(index);
        // 2. 存放未包含的顶点
        Set<Integer> setY = new HashSet<>();
        for(int i = 0; i < n; i++){
            if(i == index){
                continue;
            }else{
                setY.add(i);
            }
        }
        // 3. 开始搜索起始顶点相连顶点
        PriorityQueue<Edge> minQ = new PriorityQueue<>((a, b) -> a.weight - b.weight);
        for(int j = 0; j < n; j++){
            if(matrix[index][j] != Integer.MAX_VALUE){
                Edge edge = new Edge(index, j, matrix[index][j]);
                minQ.offer(edge);
            }
        }
        // 4. 搜索相邻顶点
        int count = 0;
        int totalWeight = 0;
        while(count < n - 1 && !minQ.isEmpty()){
            Edge edge = minQ.poll();
            if(!setX.contains(edge.destIndex)){
                minTree.addEdgeByIndex(edge.srcIndex, edge.destIndex, edge.weight);
                setX.add(edge.destIndex);
                setY.remove(edge.destIndex);
                totalWeight += edge.weight;
                count++;

                System.out.println(this.arrayV[edge.srcIndex] + "->" + this.arrayV[edge.destIndex] + ", " + edge.weight);

                if(count == n - 1){
                    return totalWeight;
                }

                for(int i = 0; i < n; i++){
                    if(matrix[edge.destIndex][i] != Integer.MAX_VALUE){
                        Edge tmp = new Edge(edge.destIndex, i, matrix[edge.destIndex][i]);
                        minQ.offer(tmp);
                    }
                }
            }
        }

        return -1;
    }

    // 最短路径问题
    public void dijkstra(char vSrc, int[] dist, int[] path){
        int n = this.arrayV.length;
        boolean[] check = new boolean[n];

        int index = getIndexOfV(vSrc);

        // 初始化距离数组，和路径数组
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[index] = 0;
        Arrays.fill(path, -1);
        path[index] = index;

        // n 个顶点，要找 n 次离得起点最近的点，每次找到之后都需要置 true，找到之后松弛连接的边
        for(int i = 0; i < n; i++){
            // 找到距离最近的顶点
            int min = Integer.MAX_VALUE;
            int u = index;
            for(int j = 0; j < n; j++){
                if(check[j] == false && min > dist[j]){
                    min = dist[j];
                    u = j;
                }
            }
            check[u] = true;

            // 松弛 u 顶点连接的边
            for(int v = 0; v < n; v++){
                if(check[v] == false && matrix[u][v] != Integer.MAX_VALUE
                        && dist[u] + matrix[u][v] < dist[v]){
                    dist[v] = dist[u] + matrix[u][v];
                    path[v] = u;
                }
            }
        }
    }

    public boolean bellmanFord(char vSrc, int[] dist, int[] path){
        int index = getIndexOfV(vSrc);

        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[index] = 0;
        Arrays.fill(path, -1);
        path[index] = 0;

        int n = this.arrayV.length;

        // 更新 n 次，确保更新的结果
        for(int k = 0; k < n; k++){
            for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++){
                    if(matrix[i][j] != Integer.MAX_VALUE && dist[i] + matrix[i][j] < dist[j]){
                        dist[j] = dist[i] + matrix[i][j];
                        path[j] = i;
                    }
                }
            }
        }

        // 多搜一次，判断是否有负权回路
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(matrix[i][j] != Integer.MAX_VALUE && dist[i] + matrix[i][j] < dist[j]){
                    return false;
                }
            }
        }

        return true;
    }

    public void floydWarShall(int[][] dist, int[][] path) {
        int n = this.arrayV.length;

        for (int i = 0; i < n; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
            Arrays.fill(path[i], -1);
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] != Integer.MAX_VALUE) {
                    dist[i][j] = matrix[i][j];
                    path[i][j] = i;
                }else{
                    path[i][j] = -1;
                }
                if (j == i) {
                    dist[i][j] = 0;
                    path[i][j] = -1;
                }
            }
        }

        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dist[i][k] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE
                            && dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                        path[i][j] = path[k][j];
                    }
                }
            }

            // 测试 打印权值和路径矩阵观察数据
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dist[i][j] == Integer.MAX_VALUE) {
                        System.out.print(" * ");
                    } else {
                        System.out.print(dist[i][j] + " ");
                    }
                }
                System.out.println();
            }
            System.out.println("=========打印路径==========");
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    System.out.print(path[i][j] + " ");
                }
                System.out.println();
            }
            System.out.println("=================");
        }
    }

    public void printShortPath(char vSrc, int[] dist, int[] path){
        int n = this.arrayV.length;
        int index = getIndexOfV(vSrc);

        for(int i = 0; i < n; i++){
            if(i == index) continue;

            List<Integer> list = new ArrayList<>();
            int pathI = i;

            while(pathI != index){
                list.add(pathI);
                pathI = path[pathI];
            }
            list.add(index);

            Collections.reverse(list);
            for(int x : list){
                System.out.print(this.arrayV[x] + "->");
            }
            System.out.println(dist[i]);
        }
    }

    public static void testGraphMinTree() {
        String str = "abcdefghi";
        char[] array =str.toCharArray();
        GraphByMatrix g = new GraphByMatrix(str.length(),false);
        g.initArrayV(array);
        g.addEdge('a', 'b', 4);
        g.addEdge('a', 'h', 8);
        //g.addEdge('a', 'h', 9);
        g.addEdge('b', 'c', 8);
        g.addEdge('b', 'h', 11);
        g.addEdge('c', 'i', 2);
        g.addEdge('c', 'f', 4);
        g.addEdge('c', 'd', 7);
        g.addEdge('d', 'f', 14);
        g.addEdge('d', 'e', 9);
        g.addEdge('e', 'f', 10);
        g.addEdge('f', 'g', 2);
        g.addEdge('g', 'h', 1);
        g.addEdge('g', 'i', 6);
        g.addEdge('h', 'i', 7);
        GraphByMatrix  kminTree = new GraphByMatrix(str.length(),false);
        //int totalWeight = g.kruskal(kminTree);
        int totalWeight = g.prime(kminTree, 'a');
        System.out.println(totalWeight);
        kminTree.printGraph();
    }

    public static void testGraphDijkstra() {
        String str = "syztx";
        char[] array = str.toCharArray();
        GraphByMatrix g = new GraphByMatrix(str.length(),true);
        g.initArrayV(array);
        g.addEdge('s', 't', 10);
        g.addEdge('s', 'y', 5);
        g.addEdge('y', 't', 3);
        g.addEdge('y', 'x', 9);
        g.addEdge('y', 'z', 2);
        g.addEdge('z', 's', 7);
        g.addEdge('z', 'x', 6);
        g.addEdge('t', 'y', 2);
        g.addEdge('t', 'x', 1);
        g.addEdge('x', 'z', 4);


    // 搞不定负权值
//    String str = "sytx";
//    char[] array = str.toCharArray();
//    GraphByMatrix g = new GraphByMatrix(str.length(),true);
//    g.initArrayV(array);
//    g.addEdge('s', 't', 10);
//    g.addEdge('s', 'y', 5);
//    g.addEdge('t', 'y', -7);
//    g.addEdge('y', 'x', 3);

        int[] dist = new int[array.length];
        int[] parentPath = new int[array.length];
        g.dijkstra('s', dist, parentPath);
        g.printShortPath('s', dist, parentPath);
    }

    public static void testGraphBellmanFord() {
        String str = "syztx";
        char[] array = str.toCharArray();
        GraphByMatrix g = new GraphByMatrix(str.length(), true);
        g.initArrayV(array);
        g.addEdge('s', 't', 6);
        g.addEdge('s', 'y', 7);
        g.addEdge('y', 'z', 9);
        g.addEdge('y', 'x', -3);
        g.addEdge('z', 's', 2);
        g.addEdge('z', 'x', 7);
        g.addEdge('t', 'x', 5);
        g.addEdge('t', 'y', 8);
        g.addEdge('t', 'z', -4);
        g.addEdge('x', 't', -2);

        //负权回路实例
//        g.addEdge('s', 't', 6);
//        g.addEdge('s', 'y', 7);
//        g.addEdge('y', 'z', 9);
//        g.addEdge('y', 'x', -3);
//        g.addEdge('y', 's', 1);
//        g.addEdge('z', 's', 2);
//        g.addEdge('z', 'x', 7);
//        g.addEdge('t', 'x', 5);
//        g.addEdge('t', 'y', -8);
//        g.addEdge('t', 'z', -4);
//        g.addEdge('x', 't', -2);
        int[] dist = new int[array.length];
        int[] parentPath = new int[array.length];
        boolean flg = g.bellmanFord('s', dist, parentPath);
        if (flg) {
            g.printShortPath('s', dist, parentPath);
        } else {
            System.out.println("存在负权回路");
        }
    }

    public static void testGraphFloydWarShall() {
        String str = "12345";
        char[] array = str.toCharArray();
        GraphByMatrix g = new GraphByMatrix(str.length(),true);
        g.initArrayV(array);
        g.addEdge('1', '2', 3);
        g.addEdge('1', '3', 8);
        g.addEdge('1', '5', -4);
        g.addEdge('2', '4', 1);
        g.addEdge('2', '5', 7);
        g.addEdge('3', '2', 4);
        g.addEdge('4', '1', 2);
        g.addEdge('4', '3', -5);
        g.addEdge('5', '4', 6);

        int[][] dist = new int[array.length][array.length];
        int[][] parentPath = new int[array.length][array.length];
        g.floydWarShall(dist,parentPath);

        for (int i = 0; i < array.length; i++) {
            g.printShortPath(array[i],dist[i],parentPath[i]);
        }
    }

    public static void main1(String[] args) {
        char[] array = {'A', 'B', 'C', 'D'};
        GraphByMatrix graph = new GraphByMatrix(array.length, false);
        graph.initArrayV(array);

        graph.addEdge('A','B',1);
        graph.addEdge('A','D',1);
        graph.addEdge('B','A',1);
        graph.addEdge('B','C',1);
        graph.addEdge('C','B',1);
        graph.addEdge('C','D',1);
        graph.addEdge('D','A',1);
        graph.addEdge('D','C',1);

        graph.printGraph();

        System.out.println(graph.getDevOfV('A'));

        graph.bfs('A');
        graph.dfs('B');
    }

    public static void main2(String[] args) {
        testGraphMinTree();
    }

    public static void main3(String[] args) {
        //testGraphDijkstra();
        //testGraphBellmanFord();
        testGraphFloydWarShall();
    }
}
